package com.yun.algorithmproblem.leetcode;

public class Leetcode494 {

    public int findTargetSumWays2(int[] nums, int target) {
        dfs(nums, target, 0, 0);
        return count;
    }

    int count = 0;

    private void dfs(int[] nums, int target, int sum, int curr) {
        if (curr == nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        dfs(nums, target, sum+nums[curr], curr+1);
        dfs(nums, target, sum-nums[curr], curr+1);
    }

    /*
        动态规划
        所有数之和为sum,所有添加负号的元素和为neg,所有添加正号的元素和为sum-neg
        此时元素和为-neg+sum-neg=target
        neg=(sum-target)/2
        此时转化为一个背包问题
        倒序遍历
     */
    public int findTargetSumWays1(int[] nums, int target){
        return 0;
    }

    public static void main(String[] args) {
        int[] num = {1, 1, 1, 1, 1};
        Leetcode494 obj = new Leetcode494();
        obj.findTargetSumWays1(num, 3);
    }
}
